package com.lxl.todo;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
* 缺失的第一个正数
* 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
* 输入：nums = [-1,1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
* TODO 已完成
* */
public class Solution16 {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            while (nums[i] >0 && nums[i] <= len && nums[i] != nums[nums[i] -1]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i +1) {
                return i +1;
            }
        }
        return len +1;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        Solution16 solution = new Solution16();
        int i = solution.firstMissingPositive(new int[]{-1,1,2,0});
        System.out.println("i = " + i);
    }
}
